package com.github.yangyishe.p300;

import com.github.yangyishe.ListNode;

import java.util.Stack;

/**
 * 234. 回文链表
 * https://leetcode.cn/problems/palindrome-linked-list/description/?envType=study-plan-v2&envId=top-100-liked
 * 已解决，但太慢
 *
 * 给你一个单链表的头节点 head ，请你判断该链表是否为
 * 回文链表
 * 。如果是，返回 true ；否则，返回 false 。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：head = [1,2,2,1]
 * 输出：true
 * 示例 2：
 *
 *
 * 输入：head = [1,2]
 * 输出：false
 *
 *
 * 提示：
 *
 * 链表中节点数目在范围[1, 105] 内
 * 0 <= Node.val <= 9
 *
 *
 * 进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
 */
public class Problem234 {
    public static void main(String[] args) {
        ListNode instance = ListNode.getInstance(new int[]{1, 2,3, 2, 1,4});

        Problem234 problem234 = new Problem234();
        boolean palindrome = problem234.isPalindrome(instance);
        System.out.println("palindrome = " + palindrome);

    }

    /**
     * 思路：
     * 比较容易想到的一种思路是，先遍历获取节点大小count，再使用栈(或逆向遍历)保存（count+1）/2个数，再取出遍历
     * 空间复杂为O(n)
     *
     *
     *
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode head) {
        int size=0;
        ListNode temp=head;
        while(temp!=null){
            size++;
            temp=temp.next;
        }

        // 是否是偶数
        boolean isEven=(size&1)==0;
        int halfSize=size>>1;
        Stack<Integer> stack=new Stack<>();
        temp=head;
        while(temp!=null){
            if(halfSize==0){
                if(!isEven){
                    isEven=true;
                }else{
                    Integer pop = stack.pop();
                    if(pop!=temp.val){
                        return false;
                    }
                }
            }else{
                stack.push(temp.val);
                halfSize--;
            }

            temp=temp.next;
        }


        return true;
    }
}
